package com.hotcode;

import jdk.internal.org.objectweb.asm.commons.AdviceAdapter;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: huangzhigao
 * @Date: 2023/2/25 16:50
 */
public class leecode76 {
    public static String minWindow(String s, String t) {
        int[] map = new int[256];
        int minLength = -1;
        char[] target = t.toCharArray();
        char[] str = s.toCharArray();
        for (char c : target) {
            map[c]++;
        }

        int all = t.length();

        int start = -1;
        int end = -1;
        int left = 0;
        int right = 0;
        while (right != str.length) {
            map[str[right]]--;
            if (map[str[right]] >= 0) {
                all--;
            }
            //满足条件了
            if (all == 0) {
                //排除所有非map中的元素
                while (map[str[left]] < 0) {
                    map[str[left++]]++;
                }
                //left来到再移动一位不足的位置
                if (right - left + 1 < minLength || minLength == -1) {
                    start = left;
                    end = right;
                    minLength = right - left + 1;
                }
                all++;
                map[str[left++]]++;
            }
            right++;
        }
        return minLength == -1 ? "" : s.substring(start, end + 1);
    }


    public static String minWindow2(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        int start = 0;
        int minLength = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        char[] targetArr = t.toCharArray();
        char[] originalArr = s.toCharArray();
        for (Character c : targetArr) {
            Integer orDefault = need.getOrDefault(c, 0);
            need.put(c, orDefault + 1);
        }
        int valid = 0;
        while (right < originalArr.length) {
            char c = originalArr[right];
            if (need.containsKey(c)) {
                Integer orDefault = window.getOrDefault(c, 0);
                window.put(c, orDefault + 1);
                if (need.get(c) == window.get(c)) {
                    valid++;
                }
            }
            while (valid == need.size()) {
                if (right - left < minLength) {
                    start = left;
                    minLength = right - left;
                }
                char d = originalArr[left++];
                if (need.containsKey(d)) {
                    if (window.get(d) == need.get(d)) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
            right++;
        }

        return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength+1);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        minWindow2(s, t);
    }


}
